package com.wrial.kind.search;
/*
 * @Author  Wrial
 * @Date Created in 12:50 2020/8/14
 * @Description
 *  实现 int sqrt(int x) 函数。
    计算并返回 x 的平方根，其中 x 是非负整数。
    由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
    4->2   8->2
 */

public class Sqrt {
    /**
     * 二分法实现，当x>=2时它的平方根一定是<=x/2的，因此就可以根据这个条件来进行二分查找
     */
    public int mySqrt(int x) {
        if(x<2) return x;
        int left = 1;
        int right = x/2;
        while(left<=right){
            // 此处一定不能使用int 否则mid*mid越界后导致值的变化
            long mid = (left+right)/2;
            if(mid*mid==x){
                return (int)mid;
            }
            if(x<mid*mid){
                right = (int)mid-1;
            }else{
                left =(int)mid+1;
            }
        }
        return right;
    }
}
